package com.programmercarl.greed;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * https://leetcode.cn/problems/partition-labels/
 * <p>
 * 划分字母区间   AC
 *
 * @author yulongtian
 * @create 2025-02-08 20:31
 */
public class Test13 {
    public static void main(String[] args) {
        Test13 test13 = new Test13();
        System.out.println(test13.partitionLabels("ababcbacadefegdehijhklij"));
    }

    public List<Integer> partitionLabels(String s) {
        List<Integer> list = new ArrayList<>(s.length());
        int[] count = new int[26];
        for (int i = 0; i < s.length(); i++) {
            count[s.charAt(i) - 'a'] = Math.max(i, count[s.charAt(i) - 'a']);
        }
        int end = 0;
        for (int i = 0; i < s.length(); i++) {
            int j = i;
            end = Math.max(end, count[s.charAt(j) - 'a']);
            while (j < end) {
                end = Math.max(end, count[s.charAt(j) - 'a']);
                j++;
            }
            list.add(j - i + 1);
            i = j;
        }

        return list;
    }
}
